package com.sheepone.util.structure.list;

import com.sheepone.util.structure.IndexedContainer;
import com.sheepone.util.structure.node.UnidirectionalNode;

import java.util.*;

/**
 * @author Miss.杨
 * @description 单向链表
 * 1. 列表为空 head=last=null
 * 2. size=1 head=last=node[0]
 * 3. size=2 head=node[0] last=node[1]
 * 4. size=3 head=node[0] last=node[2]
 * @since 2024/3/5 - 14:58
 */
public class UnidirectionalList<T> extends IndexedContainer implements DataNodeList<T, UnidirectionalNode<T>> {
    private UnidirectionalNode<T> head;
    private UnidirectionalNode<T> tail;

    public UnidirectionalList() {
        super();
    }

    public UnidirectionalList(int capacity) {
        super(capacity);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        UnidirectionalNode<T> node = head;
        while (node != null) {
            sb.append(node.getValue()).append(" ");
            node = node.getNext();
        }
        return sb.toString();
    }


    @Override
    public boolean add(T t) {
        if (isFull()) {
            return false;
        }
        UnidirectionalNode<T> node = new UnidirectionalNode<>(t);
        if (size == 0) {
            head = tail = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
        size++;
        return true;
    }

    public boolean addFirst(T t) {
        if (isFull()) {
            return false;
        }
        return addFirst(new UnidirectionalNode<>(t));
    }

    public boolean addFirst(UnidirectionalNode<T> node) {
        if (isFull()) {
            return false;
        }
        if (size == 0) {
            head = tail = node;
        } else {
            node.setNext(head);
            head = node;
        }
        size++;
        return true;
    }

    @Override
    public void add(int index, T element) {
        checkIndex(index);
        UnidirectionalNode<T> node = getNode(index);
        UnidirectionalNode<T> newNode = new UnidirectionalNode<>(element);
        newNode.setNext(node.getNext());
        node.setNext(newNode);
        size++;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        if (!hasSpace(c.size())) {
            return false;
        }
        for (T t : c) {
            if (!add(t)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        if (!hasSpace(c.size())) {
            return false;
        }
        checkIndex(index);
        UnidirectionalNode<T> node = getNode(index);
        UnidirectionalNode<T> newNode;
        for (T t : c) {
            newNode = new UnidirectionalNode<>(t);
            newNode.setNext(node.getNext());
            node.setNext(newNode);
            size++;
            node = newNode;
        }
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (head.getValue().equals(o)) {
            head = head.getNext();
            size--;
            return true;
        } else {
            UnidirectionalNode<T> preNode = head;
            UnidirectionalNode<T> node = head.getNext();
            while (node != null) {
                if (node.getValue().equals(o)) {
                    preNode.setNext(node.getNext());
                    size--;
                    return true;
                }
                preNode = node;
                node = node.getNext();
            }
        }
        return false;
    }

    @Override
    public T remove(int index) {
        checkIndex(index);
        UnidirectionalNode<T> preNode = getNode(index - 1);
        preNode.setNext(preNode.getNext().getNext());
        return preNode.getNext().getValue();
    }


    @Override
    public boolean removeAll(Collection<T> c) {
        if (c.isEmpty()) {
            return false;
        }
        for (Object o : c) {
            if (!remove(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean contains(Object o) {
        UnidirectionalNode<T> node = head;
        while (node != null) {
            if (node.getValue().equals(o)) {
                return true;
            }
            node = node.getNext();
        }
        return false;
    }

    @Override
    public boolean containsAll(Collection<T> c) {
        if (c.isEmpty()) {
            return false;
        }
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public void clear() {
        tail = null;
        head = null;
        size = 0;
    }

    @Override
    public T get(int index) {
        return getNode(index).getValue();
    }


    @Override
    public T set(int index, T element) {
        checkIndex(index);
        UnidirectionalNode<T> node = getNode(index);
        T data = node.getValue();
        node.setValue(element);
        return data;
    }


    @Override
    public int indexOf(Object o) {
        UnidirectionalNode<T> node = head;
        int index = 0;
        while (node != null) {
            if (node.getValue().equals(o)) {
                return index;
            }
            node = node.getNext();
            index++;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        int index = size - 1;
        while (index >= 0) {
            if (get(index).equals(o)) {
                return index;
            }
            index--;
        }
        return -1;
    }

    @Override
    public boolean addNode(UnidirectionalNode<T> node) {
        if (node == null || isFull()) {
            return false;
        }
        if (head == null) {
            head = node;
        } else {
            tail.setNext(node);
        }
        tail = node;
        size++;
        return true;
    }

    @Override
    public void addNode(int index, UnidirectionalNode<T> node) {
        if (node == null || isFull()) {
            return;
        }
        checkIndex(index);
        UnidirectionalNode<T> preNode = getNode(index);
        node.setNext(preNode.getNext());
        preNode.setNext(node);
    }


    @Override
    public void addAllNode(Collection<? extends UnidirectionalNode<T>> c) {
        for (UnidirectionalNode<T> t : c) {
            addNode(t);
        }
    }

    @Override
    public void addAllNode(int index, Collection<? extends UnidirectionalNode<T>> c) {
        UnidirectionalNode<T> node = getNode(index);
        UnidirectionalNode<T> last = node.getNext();
        for (UnidirectionalNode<T> t : c) {
            node.setNext(t);
            node = t;
        }
        node.setNext(last);
    }

    @Override
    public boolean containsNode(UnidirectionalNode<T> o) {
        UnidirectionalNode<T> node = head;
        while (node != null) {
            if (node.equals(o)) {
                return true;
            }
            node = node.getNext();
        }
        return false;
    }

    @Override
    public boolean containsAllNode(Collection<?> c) {
        if (c.isEmpty()) {
            return false;
        }
        for (Object o : c) {
            if (!containsNode((UnidirectionalNode<T>) o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public UnidirectionalNode<T> getNode(int index) {
        int no = 0;
        UnidirectionalNode<T> node = head;
        while (no++ != index) {
            node = node.getNext();
        }
        return node;
    }

    @Override
    public int indexOfNode(UnidirectionalNode<T> o) {
        UnidirectionalNode<T> node = head;
        int index = 0;
        while (node != null) {
            if (node.equals(o)) {
                return index;
            }
            node = node.getNext();
            index++;
        }
        return -1;
    }

    @Override
    public Iterator<UnidirectionalNode<T>> nodeIterator() {
        return null;
    }

    @Override
    public boolean removeNode(UnidirectionalNode<T> o) {
        if (head.equals(o)) {
            head = head.getNext();
            size--;
            return true;
        }
        UnidirectionalNode<T> node = head.getNext();
        UnidirectionalNode<T> preNode = head;
        while (node != null) {
            if (node.equals(o)) {
                preNode.setNext(node.getNext());
                size--;
                return true;
            }
            preNode = node;
            node = node.getNext();
        }
        return false;
    }

    @Override
    public UnidirectionalNode<T> removeNode(int index) {
        checkIndex(index);
        UnidirectionalNode<T> node;
        if (index == 0) {
            node = head;
            head = head.getNext();
        } else {
            UnidirectionalNode<T> preNode = getNode(index - 1);
            node = preNode.getNext();
            preNode.setNext(node.getNext());
        }
        size--;
        return node;
    }


    /**
     * 检测单向链表是否存在环
     *
     * @return
     * @url <a href="https://leetcode-cn.com/problems/linked-list-cycle/">...</a>
     * @time-complexity O(n)
     * @space-complexity O(1)
     */
    public int detectCycle() {
        UnidirectionalNode<T> fast = head, slow = head;
        do {
            // fast 指针走过链表末端，说明链表无环，此时直接返回 null
            if (fast == null || fast.getNext() == null) {
                return -1;
            }
            // 令 fast 每轮走 2 步，slow 每轮走 1 步
            // 如果链表存在环，则双指针一定会相遇。
            // 因为每走 1 轮，fast 与 slow 的间距 +1，fast 一定会追上 slow
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        } while (fast != slow);
        // 当fast == slow时， 两指针在环中第一次相遇

        // 设链表共有 a+b 个节点，
        // 其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点

        // 设两指针分别走了 f（fast），s（slow） 步
        // 1. f==2s
        // 2. f = s + n * b （n为fast比slow多绕了多少次环）
        // 可以得出 s = n * b , f = 2 * n * b , 即fast比slow夺走了n圈环

        // 如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时的步数 是：k=a+n*b

        // 那么再让他们都走a步，那么它们相遇点就是环的入口
        // 因此我们让fast重回head位置走，那么fast和slow第二次相遇点就一定是环的入口点
        fast = head;
        int index = 0;
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
            index++;
        }
        return index;
    }

    /**
     * 反转单向链表
     *
     * @return
     */
    public UnidirectionalList<T> reverse() {
        UnidirectionalList<T> list = new UnidirectionalList<T>();
        UnidirectionalNode<T> node = head;
        while (node != null) {
            list.addFirst(node);
            node = node.getNext();
        }
        return list;
    }

    /**
     * 寻找单向链表的中间节点
     */
    public UnidirectionalNode<T> middleNode() {
        if (isEmpty()) {
            return null;
        }
        UnidirectionalNode<T> fast;
        UnidirectionalNode<T> slow;
        fast = slow = head;
        while (fast != null && fast.getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
        }
        return slow;
    }
}
